package org.hot100_1;

import java.util.Deque;
import java.util.LinkedList;

public class leetcode11 {
    //hard 239
    public int[] maxSlidingWindow(int[] nums, int k) {

        int n = nums.length;
        int [] res = new int[n-k+1];
        int index = 0;

        Deque<Integer> deque = new LinkedList<>();

        //i为当前滑动窗口的右边界
        for (int i = 0; i < n; i++) {
            //i-k+1为当前滑动窗口的左边界，只需要判断队列的队首元素是否在滑动窗口的范围内即可
            //因为队首元素是当前窗口的最大值。但是队首的元素可能不在当前的窗口内，需要不断的更新使得队首的元素在当前的窗口范围内
            while (!deque.isEmpty() && deque.peek()<i-k+1){
                deque.pollFirst();
            }

            //如果当前的元素大于队尾的元素，对队尾的元素进行更新操作，使得队列中的数据是有序的
            while (!deque.isEmpty() && nums[i]>=nums[deque.peekLast()]){
                deque.pollLast();
            }

            deque.offer(i);

            //只有达到窗口时才开始更新数据
            if (i>=k-1){
                res[index] = nums[deque.peekFirst()];
                index++;
            }
        }


        return res;
    }
}
